This invention relates to encoding and decoding of data for error-correction purposes in data storage and communications systems. Methods, apparatus and computer programs are provided for encoding data supplied to a data channel, together with corresponding decoding systems and data storage and communications systems employing same.
Error-correction encoding is employed in data storage and communications systems to improve the accuracy with which data can be recovered from the data channel. By encoding data in accordance with an error-correction code (ECC) before supply to the channel, errors at the channel output can be identified and corrected to an extent dependent on the properties of the code. Numerous such ECC schemes are known. One well-known class of ECC scheme is based on product codes. A product code uses two component ECC codes to encode rows and columns of a notional two-dimensional array of input data. The basic principle of these codes is indicated in FIG. 1 of the accompanying drawings and is described briefly below.
The basic structure of an exemplary product code is illustrated schematically in FIG. 1. The input data symbols (which in general may be qary symbols, having q possible symbol values, where q≥2) are assigned to respective symbol locations in a notional array having n2 rows and n1 columns of symbol locations. In this example, k2×k1 data symbols are assigned to respective locations in a k2 by k1 subarray at the intersection of the first k2 rows and first k1 columns of the n2 by n1 array. The resulting array of input data symbols is encoded by separately encoding the rows and columns of the array. A first ECC code C1 is used to encode the k1-symbol data word in each row of the array into a length-n1 C1 codeword. This example uses systematic encoding, whereby the input data is retained in the codeword. In particular, the n1 code symbols of a C1 codeword are obtained by adding (n1−k1) parity symbols after the k1-symbol data word in a given row. A second ECC code C2 is then used to encode the k2-symbols in each column of the array into a length-n2 C2 codeword, here by adding (n2−k2) parity symbols at the end of each column. The resulting n2×n1 code symbols in the array form the output codeword of the product code. In an extension of this basic idea, an interleaved product code applies the C2 code over s>1 evenly spaced columns of the array, resulting in n2/s C2 codewords.
Product codes can offer practical encoder/decoder implementations, their decoders being hard-decision based and thus avoiding the various complexity/latency issues associated with soft-decision decoding. Some decoders for interleaved product codes use the technique of iterative decoding based on a graph defined from the basic code structure. Briefly, a bipartite graph can be defined with n2 right nodes, each corresponding to a C1 codeword, and n2/s left nodes corresponding to respective C2 codewords. Each right node is connected to each left node by s edges. The s edges connecting a pair of nodes represent the s common symbols at the intersections of the C1 and C2 codewords for those nodes in the notional array described above. Iterative decoding is performed based on the graph by decoding the C1 codewords one-by-one, then decoding the C2 codewords one-by-one. Each time a codeword is successfully decoded, the edges leaving the appropriate node are corrected. The process iterates until decoding is complete.
Another ECC scheme based on product codes is proposed in the context of optical transmission networks in ‘Error correcting coding for OTN’, J. Justesen, IEEE Communications Magazine, September 2010, and ‘Performance of Product Codes and Related Structures with Iterative Decoding’, J. Justesen, IEEE Transactions on Communications, 2011. These codes, referred to as “half product codes”, are based on product codes which use identical codes for the row code C1 and the column code C2. If each component code C1 and C2 is a rate kln code with a code length (i.e., number of symbols in a codeword) of n, and a dimension (i.e., number of data symbols encoded into each codeword) of k, then the resulting product code C has length N=n2, dimension K=k2, and rate (k/n)2. A codeword of C can be defined by an (n by n)-symbol matrix X corresponding to the notional array described above, where each row and column of X is a codeword of the row/column code. The corresponding half product code CH is then defined byCH={X−XT: X∈C}
where XT is the transpose matrix of X. Note that, if X is a codeword then so is XT because the row and column codes are the same. By construction, every codeword YH of CH has a zero diagonal (where the diagonal is defined here as the line of symbols extending diagonally across the (n by n)-symbol matrix YH from the top left symbol to the bottom right symbol). That is, all symbols on the diagonal are of value zero. Since it follows from the definition of CH that YH=YHT, the set of n(n−1)/2 symbols in the triangular subarray on each side of the diagonal is the same. These n(n−1)/2 symbols thus define the codeword YH whereby the half product code has an effective length of NH=n(n−1)/2.
Encoding is done as for product codes, but the input data is restricted to the triangular subarray on one side of the diagonal, giving a dimension of KH=k(k−1)/2 for the half product code.